from collections import deque
maze=[
    [1,1,1,1,1,1,1,1,1,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,0,0,1,1,0,0,1],
    [1,0,1,1,1,0,0,0,0,1],
    [1,0,0,0,1,0,0,0,0,1],
    [1,0,1,0,0,0,1,0,0,1],
    [1,0,1,1,1,0,1,1,0,1],
    [1,1,0,0,0,0,0,0,0,1],
    [1,1,1,1,1,1,1,1,1,1]
]
dirs=[lambda x,y:(x+1,y),
      lambda x,y:(x-1,y),
      lambda x,y:(x,y-1),
      lambda x,y:(x,y+1)]

def print_r(path):
    curNode=path[-1]
    real_path=[]
    while curNode[2]!=-1:
        real_path.append((curNode[0],curNode[1]))
        curNode=path[curNode[2]]
        #把起点放进去
    real_path.append(curNode[0:2])
    real_path.reverse()
    for node in real_path:
        print(node,end=',')

def maze_path_queue(x1,y1,x2,y2):
    queue=deque()
    path=[]
    queue.append((x1,y1,-1))
    while len(queue)>0:
        curNode=queue.pop()
        path.append(curNode)
        if curNode[0]==x2 and curNode[1]==y2:
            #找到终点
            print_r(path)
            return True
        for dir in dirs:
            nextNode=dir(curNode[0],curNode[1])
            if maze[nextNode[0]][nextNode[1]]==0:
                #后续节点进队，记录哪个节点带他来的
                queue.append((nextNode[0],nextNode[1],len(path)-1))
                maze[nextNode[0]][nextNode[1]]=2
    else:
        print('没有路')
        return False
maze_path_queue(1,1,8,8)